Modular Binomials https://cryptohack.org/courses/modular/bionomials/

題意:

題目只告訴我們重新排列以下方程式來獲得p,q，並給了我們一個data.txt，裡面有N,e1,e2,c1,c2的值。
而要回傳的flag為crypto{p,q}。

解題思路:

參考了網路上找到的解法，主要有兩種解題思路。
1.題目提及N=p.q，所以可以試著使用因數分解工具

2.解數學式...

在網路上找到他人解數學式的方法，我又自己手算了一遍，了解整個運算的流程。之後再將這個解題過程轉換成程式(網路上可以找到很多人寫好的程式碼)

###Modular Binomials
from math import gcd

n = 14905562257842714057932724129575002825405393502650869767115942606408600343380327866258982402447992564988466588305174271674657844352454543958847568190372446723549627752274442789184236490768272313187410077124234699854724907039770193680822495470532218905083459730998003622926152590597710213127952141056029516116785229504645179830037937222022291571738973603920664929150436463632305664687903244972880062028301085749434688159905768052041207513149370212313943117665914802379158613359049957688563885391972151218676545972118494969247440489763431359679770422939441710783575668679693678435669541781490217731619224470152467768073
e1 = 12886657667389660800780796462970504910193928992888518978200029826975978624718627799215564700096007849924866627154987365059524315097631111242449314835868137
e2 = 12110586673991788415780355139635579057920926864887110308343229256046868242179445444897790171351302575188607117081580121488253540215781625598048021161675697
c1 = 14010729418703228234352465883041270611113735889838753433295478495763409056136734155612156934673988344882629541204985909650433819205298939877837314145082403528055884752079219150739849992921393509593620449489882380176216648401057401569934043087087362272303101549800941212057354903559653373299153430753882035233354304783275982332995766778499425529570008008029401325668301144188970480975565215953953985078281395545902102245755862663621187438677596628109967066418993851632543137353041712721919291521767262678140115188735994447949166616101182806820741928292882642234238450207472914232596747755261325098225968268926580993051
c2 = 14386997138637978860748278986945098648507142864584111124202580365103793165811666987664851210230009375267398957979494066880296418013345006977654742303441030008490816239306394492168516278328851513359596253775965916326353050138738183351643338294802012193721879700283088378587949921991198231956871429805847767716137817313612304833733918657887480468724409753522369325138502059408241232155633806496752350562284794715321835226991147547651155287812485862794935695241612676255374480132722940682140395725089329445356434489384831036205387293760789976615210310436732813848937666608611803196199865435145094486231635966885932646519

q1 = pow(c1, e2, n)
q2 = pow(c2, e1, n)

d = pow(5, e1 * e2, n) * q1 - pow(2, e1 * e2, n) * q2

q = gcd(d, n)
p = n // q

assert(p * q == n)
print(f"crypto{{{p},{q}}}")

參考資料:

因數分解工具:
https://factordb.com/index.php?query=14905562257842714057932724129575002825405393502650869767115942606408600343380327866258982402447992564988466588305174271674657844352454543958847568190372446723549627752274442789184236490768272313187410077124234699854724907039770193680822495470532218905083459730998003622926152590597710213127952141056029516116785229504645179830037937222022291571738973603920664929150436463632305664687903244972880062028301085749434688159905768052041207513149370212313943117665914802379158613359049957688563885391972151218676545972118494969247440489763431359679770422939441710783575668679693678435669541781490217731619224470152467768073
較為複雜的數學式推演過程:
https://www.ctfrecipes.com/cryptography/general-knowledge/maths/modular-arithmetic/modular-binomial
他人的博客:
https://www.cnblogs.com/Cryglz/p/17375266.html
他人的解題過程:
https://hackmd.io/@ADP/r1JV8qFk0?utm_source=preview-mode&utm_medium=rec#Adriens-Signs
前人的文章: https://ithelp.ithome.com.tw/articles/10327091?sc=rss.qu

後話:

今天花了一些時間理解如何解這題的數學式，然後發現之前的標題有打錯，所以全部更正了一遍。剛才發現有web版的SageMath，所以在Day15的文章那邊更新了一下。